CS154Spring 2011Lecture Notes

Videos of lectures are available. As they are on my office machine and I don't want robots to try to download them, the directory is password protected. The login is guest and the password is guest.

Below are my lecture notes for the class so far. They should serve as a rough guide to what was covered on any given day. Frequently, however, I say more in class than is in these notes. Also, I tend to dynamically correct typos on the board that might appear in these lecture notes. So caveat emptor.

Week 1: [Jan. 26 -- Automata theory and Computability]

Week 2: [Jan. 31 -- Sets, Relations, Functions Graphs] [Feb 2 -- Functions, Graphs, Trees, and Proofs]

Week 3: [Feb 7 -- Finite Automata] [Feb 9 -- More Deterministic Finite Automata]

Week 4: [Feb 14 -- Nondeterministic Finite Automata] [Feb 16 --Minimization, Closure Proofs, Regular Expressions]

Week 5: [Feb 21 -- Regular Expressions and Grammars] [Feb 23 -- Homomorphism, Quotients, Pumping Lemma]

Week 6: [Feb 28 -- Context-Free Grammars] [Mar 2 -- Transforming Grammars]

Week 7: [Mar 7 -- Chomsky Normal Form] [Mar 9 -- Pushdown Automata]

Week 8: [Mar 14 -- More PDAs, Pumping Lemma for CFGs] [Mar 16 -- Practice Midterm Day]

Week 9: [Mar 21 - Midterm] [Mar 23 -- Compression, CFL Closure Properties, and CFL Algorithms]

Week 10: Spring Break

Week 11: [Apr 4 -- Turing Machines] [Apr 6 -- Building Bigger Machines From Smaller Ones]

Week 12: [Apr 11 -- Equivalence of Turing Machine Variants] [Apr 13 -- More Computational Variants]

Week 13: [Apr 18 -- More RAMs and Nondeterministic TMs] [Apr 20 -- Decidability, UTMs, and Diagonalization]

Week 14: [Apr 25 -- Hierarchy Theorems, co-r.e. sets, Reductions] [Apr 27 -- Complete Problems, More Reductions]

Week 15: [May 2 -- Computation Histories] [May 4 -- PCP, Rice's Theorem]

Week 16: [May 9 -- The Recursion Theorem] [May 11 -- Kolmogorov Complexity]